import collections


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class ValidBST:  # 验证二叉搜索树
    pre = float("-inf")

    def validate(self, root):
        """
        利用二叉搜索树中序遍历得到的数组必为升序性质
        :param root: TreeNode
        :return: True or False
        """
        if root is None:
            return True
        if self.validate(root.left) is False:
            return False
        if root.val <= self.pre:
            return False
        self.pre = root.val
        return self.validate(root.right)

    @classmethod
    def helper(cls, node, lower=float('-inf'), upper=float('inf')):
        if not node:
            return True
        val = node.val
        if val <= lower or val >= upper:
            return False
        if not cls.helper(node.left, lower, val):
            return False
        if not cls.helper(node.right, val, upper):
            return False
        return True


def list_to_tree(nums):
    """从一个列表层序生成二叉树"""
    nums = nums[::-1]
    tree = TreeNode(nums.pop())
    stack = [tree]
    while nums or stack:
        stack_ = []
        for i in stack:
            left = nums.pop() if len(nums) > 0 else None
            if left or str(left) == "0":
                left = TreeNode(left)
                stack_.append(left)
            i.left = left
            right = nums.pop() if len(nums) > 0 else None
            if right or str(right) == "0":
                right = TreeNode(right)
                stack_.append(right)
            i.right = right
        stack = stack_
    return tree


class TreeToList:
    """中序"""

    def __init__(self):
        self.res = []

    def tree_to_list(self, root):
        if not root:
            self.res.append(None)
            return
        self.tree_to_list(root.left)
        self.res.append(root.val)
        self.tree_to_list(root.right)

    def run(self, root):
        self.res = []
        self.tree_to_list(root)
        return self.res


# 前序 根左右
def preorder_dg(root):
    if not root:
        return
    print(root.val)
    preorder_dg(root.left)
    preorder_dg(root.right)


def preorder_dd(root):
    stack = [root]
    while stack:
        s = stack.pop()
        if s:
            print(s.val)
            stack.append(s.right)
            stack.append(s.left)


def predg_ancestors(root, target, ancestors=[]):
    """前序递归获得指定节点值的所有祖先节点值，假定所有节点的值不相同"""
    if not root:
        return
    ancestors.append(root.val)
    if root.val == target:
        return ancestors
    tmp = predg_ancestors(root.left, target, ancestors.copy())
    return tmp if tmp else predg_ancestors(root.right, target, ancestors.copy())


# 中序 左根右
def midorder_dg(root):
    if not root:
        return
    midorder_dg(root.left)
    print(root.val)
    midorder_dg(root.right)


def midorder_dd(root):
    stack = []
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        print(root.val)
        root = root.right


# 后序 左右根
def posorder_dg(root):
    if not root:
        return
    posorder_dg(root.left)
    posorder_dg(root.right)
    print(root.val)


# 层次遍历
def bfs(root):
    queue = [root]
    while queue:
        n = len(queue)
        for i in range(n):
            q = queue.pop(0)  # 双端队列 popleft
            if q:
                print(q.val)
                queue.append(q.left if q.left else None)
                queue.append(q.right if q.right else None)


# 二叉树的最大深度
def max_depth(tree):
    if not tree:
        return 0
    return 1 + max(max_depth(tree.left), max_depth(tree.right))


# 生成镜像树
def mirror(tree):
    if tree is None:
        return
    tree.left, tree.right = mirror(tree.right), mirror(tree.left)
    return tree


# 判断是否是对称二叉树
def is_symmetree(tree):
    def helper(l, r):  # 对称节点是否满足要求
        if not l and not r: return True
        if not l or not r or l.val != r.val: return False
        return helper(l.left, r.right) and helper(l.right, r.left)

    return helper(tree.left, tree.right) if tree else True


# 前序加中序建树
def build_tree(preorder, inorder):
    if len(inorder) == 0:
        return
    ind = inorder.index(preorder[0])
    tree = TreeNode(preorder[0])
    tree.left = build_tree(preorder[1: ind + 1], inorder[: ind])
    tree.right = build_tree(preorder[ind + 1:], inorder[ind + 1:])
    return tree


if __name__ == "__main__":
    root = TreeNode("A")
    root.left = TreeNode("B")
    root.right = TreeNode("C")
    root.left.left = TreeNode("D")
    root.left.right = TreeNode("E")
    root.right.right = TreeNode("F")

    print("前序")
    preorder_dg(root)
    print()
    preorder_dd(root)
    print("中序")
    midorder_dg(root)
    print()
    midorder_dd(root)
    print("后序")
    posorder_dg(root)

    # a = [1, 2, 3]
    # while a:
    #     b = a.pop()
    #     print(b)